package _go

/*面试题 04.02. 最小高度树
难度
简单

83

收藏

分享
切换为英文
接收动态
反馈
给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。

示例:
给定有序数组: [-10,-3,0,5,9],

一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

          0
         / \
       -3   9
       /   /
     -10  5 */
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sortedArrayToBST(nums []int) *TreeNode {
	if nums == nil {
		return nil
	}
	l := len(nums)
	return build(nums, 0, l-1)
}
func build(nums []int, l, r int) *TreeNode {
	if l > r {
		return nil
	}
	min := l + (r-l)/2
	return &TreeNode{
		Val:   nums[min],
		Left:  build(nums, l, min-1),
		Right: build(nums, min+1, r),
	}
}
